package implementations;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import sun.reflect.generics.reflectiveObjects.NotImplementedException;

import interfaces.Edge;
import interfaces.Graph;
import interfaces.Vertex;

/**
 * @author Kai Bielenberg
 * @author Oliver Behnke
 * 
 * @param <E>
 * @param <V>
 */
public abstract class AbstractGraph<E, V> implements Graph<E, V> {

	// TODO Caching wieder raus?
	protected Set<Edge<E, V>> edges = new HashSet<Edge<E, V>>();
	protected Set<Vertex<V>> vertices = new HashSet<Vertex<V>>();

	private int numberOfAcesses = 0;

	private long startTimeLastAlgorithm = 0;
	private long endTimeLastAlgorithm = 0;

	private int startNumberOfAccesses = 0;
	private int endNumberOfAccesses = 0;

	public long runtimeLastAlgorithm() {
		return this.endTimeLastAlgorithm - this.startTimeLastAlgorithm;
	}

	@Override
	public int lastNumberOfAccesses() {
		return this.endNumberOfAccesses - this.startNumberOfAccesses;
	}

	protected void startMeasuring() {
		this.startNumberOfAccesses = numberOfAccesses();
		this.startTimeLastAlgorithm = System.nanoTime();
	}

	protected void endMeasuring() {
		this.endNumberOfAccesses = numberOfAccesses();
		this.endTimeLastAlgorithm = System.nanoTime();
	}

	@Override
	public void add(Edge<E, V> e) {

		Set<Vertex<V>> temp = new HashSet<Vertex<V>>(e.vertices());
		temp.retainAll(this.vertices());

		if (temp.isEmpty())
			throw new IllegalArgumentException(
					"Edge doesn't have any vertex, which is already included in the graph");
		edges.add(e);
		vertices.addAll(e.vertices());
	}

	@Override
	public boolean includes(Vertex<V> v) {
		return this.vertices().contains(v);
	}

	@Override
	public boolean includes(Edge<E, V> e) {
		return this.edges().contains(e);
	}

	@Override
	public Collection<Edge<E, V>> edges() {
		return this.edges;
	}

	@Override
	public Collection<Vertex<V>> vertices() {
		return this.vertices;
	}

	protected Map<Vertex<V>, Set<Edge<E, V>>> calcIncidenceList() {
		// Incidence Liste wird bei bedarf errechnet und verwendet.
		// Implementierung hier als Map, jedem Vertex wird ein Set von
		// Edges(maximal 2) zugeordnet.
		Map<Vertex<V>, Set<Edge<E, V>>> result = new HashMap<Vertex<V>, Set<Edge<E, V>>>();
		for (Vertex<V> v : this.vertices()) {
			result.put(v, new HashSet<Edge<E, V>>());
		}
		for (Edge<E, V> e : this.edges()) {
			for (Vertex<V> v : e.vertices()) {
				result.get(v).add(e);
			}
		}
		return result;
	}

	protected Map<Vertex<V>, Set<Edge<E, V>>> calcStartIncidenceList() {
		// Incidence Liste wird bei bedarf errechnet und verwendet.
		// Implementierung hier als Map, jedem Vertex wird ein Set von
		// Edges(maximal 2) zugeordnet.
		Map<Vertex<V>, Set<Edge<E, V>>> result = new HashMap<Vertex<V>, Set<Edge<E, V>>>();
		for (Vertex<V> v : startVertices()) {
			result.put(v, new HashSet<Edge<E, V>>());
		}
		for (Edge<E, V> e : this.edges()) {
			result.get(e.start()).add(e);

		}
		return result;
	}

	protected Map<Vertex<V>, Set<Edge<E, V>>> calcEndIncidenceList() {
		// Incidence Liste wird bei bedarf errechnet und verwendet.
		// Implementierung hier als Map, jedem Vertex wird ein Set von
		// Edges(maximal 2) zugeordnet.
		Map<Vertex<V>, Set<Edge<E, V>>> result = new HashMap<Vertex<V>, Set<Edge<E, V>>>();
		for (Vertex<V> v : endVertices()) {
			result.put(v, new HashSet<Edge<E, V>>());
		}
		for (Edge<E, V> e : this.edges()) {
			result.get(e.end()).add(e);

		}
		return result;
	}

	protected void recordAccess() {
		this.numberOfAcesses += 1;
	}

	protected void recordAccess(int i) {
		for (int n = 0; n < i; n++)
			this.numberOfAcesses += 1;
	}

	public int numberOfAccesses() {
		int result = 0;
		for (Edge<E, V> e : edges) {
			result = result + e.numberOfAccesses();
		}
		for (Vertex<V> v : vertices) {
			result = result + v.numberOfAccesses();
		}
		return result + this.numberOfAcesses;
	}

	// public String traverse() { // Ausgabe Graph
	// Vertex<V> v= edges().iterator().next().start();
	// return traverse_(v, new HashSet<Edge<E,V>>(this.edges()),
	// calcStartIncidenceList(),0);
	// }

	public abstract String traverse(); // Ausgabe Graph

	@Override
	public List<Edge<E, V>> eulerTour() {
	    startMeasuring();
		List<Edge<E, V>> result = new LinkedList<Edge<E, V>>();
		if (isDirected())
			throw new NotImplementedException();
		if (this.hasEulerTour()) {
			Vertex<V> v = vertices().iterator().next();
			Edge<E, V> e = null;
			Map<Vertex<V>, Set<Edge<E, V>>> incidenceList = calcIncidenceList();
			boolean breakflag = false;
			while (!breakflag) {
				for (Edge<E, V> newEdge : incidenceList.get(v)) {
					if (incidenceList.get(newEdge.otherVertex(v)).size() > 0)
						e = newEdge;
					    
				}
				if (e == null)
					breakflag = true;
				else {
					incidenceList.get(v).remove(e);
					incidenceList.get(e.otherVertex(v)).remove(e);
					v = e.otherVertex(v);
					result.add(e);
					e = null;
				}
			}
		}
		endMeasuring();
		if (result.size() == edges.size()) return result;
		else return new LinkedList<Edge<E,V>>();
	}

	@Override
	public List<Vertex<V>> hamiltonianPath() {
	    startMeasuring();
	    List<Vertex<V>> list=new LinkedList<Vertex<V>>();
	    list.add(vertices().iterator().next());
	    List<Vertex<V>> result = hamiltonianPath_(list.get(0), list, calcIncidenceList());
	    endMeasuring();
	    return result;
	}
	
	private List<Vertex<V>> hamiltonianPath_(Vertex<V> v, List<Vertex<V>> list, Map<Vertex<V>, Set<Edge<E, V>>> incidenceList){
	    System.out.println(list);
	    if(list.size() == vertices.size()){
	        boolean returnToStart=false;
	        for(Edge<E,V> e: incidenceList.get(v)){
	            if(e.includes(list.get(0))) returnToStart=true;
	        }  
	        if(returnToStart) return list;
	    }
	    
	    for(Edge<E,V> e: incidenceList.get(v)){
	        if(!list.contains(e.otherVertex(v))){
	             List<Vertex<V>> result=new LinkedList<Vertex<V>>(list);
	             result.add(e.otherVertex(v));
	             List<Vertex<V>> temp=hamiltonianPath_(e.otherVertex(v), result, incidenceList);
	             if(!temp.isEmpty()) return temp;
	        }
	    }
	    return new LinkedList<Vertex<V>>();
	}
	

	@Override
	public String toString() {
		return this.traverse();
	}

	@Override
	public boolean equals(Object o) {
		// Quick Check for same Object
		if (o == this)
			return true;
		// Type Check
		if (!(o instanceof Graph<?, ?>))
			return false;
		// Check of the Arguments
		return this.edges().equals(((Graph<?, ?>) o).edges())
				&& this.vertices().equals(((Graph<?, ?>) o).vertices());
	}

	@Override
	public int hashCode() {
		return this.vertices().hashCode() + edges.hashCode();
	}

	private Set<Vertex<V>> startVertices() {
		Set<Vertex<V>> result = new HashSet<Vertex<V>>();
		for (Edge<E, V> e : edges()) {
			result.add(e.start());
		}
		return result;
	}

	private Set<Vertex<V>> endVertices() {
		Set<Vertex<V>> result = new HashSet<Vertex<V>>();
		for (Edge<E, V> e : edges()) {
			result.add(e.end());
		}
		return result;
	}

}
